package com.sheng.leetcode.year2022.month09.day16;

import org.junit.Test;

import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author liusheng
 * @date 2022/09/16
 *<p>
 * 850. 矩形面积 II<p>
 *<p>
 * 我们给出了一个（轴对齐的）二维矩形列表rectangles。对于rectangle[i] = [x1, y1, x2, y2]，<p>
 * 其中（x1，y1）是矩形i左下角的坐标，(xi1, yi1)是该矩形 左下角 的坐标，(xi2, yi2)是该矩形右上角 的坐标。<p>
 * 计算平面中所有rectangles所覆盖的 总面积 。任何被两个或多个矩形覆盖的区域应只计算 一次 。<p>
 * 返回 总面积 。因为答案可能太大，返回10^9+ 7 的模。<p>
 *<p>
 * 示例 1：<p>
 * 输入：rectangles = [[0,0,2,2],[1,0,2,3],[1,0,3,1]]<p>
 * 输出：6<p>
 * 解释：如图所示，三个矩形覆盖了总面积为6的区域。<p>
 * 从(1,1)到(2,2)，绿色矩形和红色矩形重叠。<p>
 * 从(1,0)到(2,3)，三个矩形都重叠。<p>
 *<p>
 * 示例 2：<p>
 * 输入：rectangles = [[0,0,1000000000,1000000000]]<p>
 * 输出：49<p>
 * 解释：答案是 10^18 对 (10^9 + 7) 取模的结果， 即 49 。<p>
 *<p>
 * 提示：<p>
 *<p>
 * 1 <= rectangles.length <= 200<p>
 * rectanges[i].length = 4<p>
 * 0 <= xi1, yi1, xi2, yi2<= 10^9<p>
 * 矩形叠加覆盖后的总面积不会超越2^63 - 1，这意味着可以用一个64 位有符号整数来保存面积结果。<p>
 *<p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/rectangle-area-ii">...</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode0850 {

    @Test
    public void test01() {
        int[][] rectangles = {{0,0,2,2},{1,0,2,3},{1,0,3,1}};
//        int[][] rectangles = {{0,0,1000000000,1000000000}};
        System.out.println(new Solution().rectangleArea(rectangles));
    }
}
class Solution {
    int MOD = (int)1e9+7;
    public int rectangleArea(int[][] rs) {
        List<Integer> list = new ArrayList<>();
        for (int[] info : rs) {
            list.add(info[0]); list.add(info[2]);
        }
        Collections.sort(list);
        long ans = 0;
        for (int i = 1; i < list.size(); i++) {
            int a = list.get(i - 1), b = list.get(i), len = b - a;
            if (len == 0) {
                continue;
            }
            List<int[]> lines = new ArrayList<>();
            for (int[] info : rs) {
                if (info[0] <= a && b <= info[2]) {
                    lines.add(new int[]{info[1], info[3]});
                }
            }
            Collections.sort(lines, (l1, l2)->{
                return l1[0] != l2[0] ? l1[0] - l2[0] : l1[1] - l2[1];
            });
            long tot = 0, l = -1, r = -1;
            for (int[] cur : lines) {
                if (cur[0] > r) {
                    tot += r - l;
                    l = cur[0]; r = cur[1];
                } else if (cur[1] > r) {
                    r = cur[1];
                }
            }
            tot += r - l;
            ans += tot * len;
            ans %= MOD;
        }
        return (int) ans;
    }
}

//作者：AC_OIer
//        链接：https://leetcode.cn/problems/rectangle-area-ii/solution/gong-shui-san-xie-by-ac_oier-9r36/
//        来源：力扣（LeetCode）
//        著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
//class Solution {
//    public int rectangleArea(int[][] rectangles) {
//        // (x1, y1, x2, y2)  -->  该矩阵的面积为 (x2 - x1) * (y2 - y1)
//        // 思路，将矩阵按照重复区域进行切割成多个矩阵
//        List<int[]> list = new ArrayList<>();
//        for (int i = 0; i < rectangles.length; i++) {
//            if (i == 0) {
//                list.add(rectangles[i]);
//            } else {
//                for (int[] ints : list) {
//                    // 判断是否重合，重合则进行切割
//                    if (true) {
//                        // 切割
//                    }
//                }
//            }
//        }
//        // 实现切割成小块后，获取面积
//        BigDecimal area = new BigDecimal("0");
//        for (int[] ints : list) {
//            area = area.add(new BigDecimal((long) (ints[2] - ints[0]) * (long) (ints[3] - ints[1])));
//        }
//        area = area.divideAndRemainder(new BigDecimal("1000000007"))[1];
//        return area.intValue();
//    }
//}
